Delay Behaviour of Asynchronous Internet Router under Self-Similar Traffic Input – Queueing System with Markovian Input and Hyper-Erlang Services

 

Ravi Kumar Gudimalla*, Malla Reddy Perati

Department of Mathematics, Kakatiya University, Warangal – 506009 (T.S.) India.

 

ABSTRACT:

In this paper, we analyze the delay behaviour of asynchronous Internet router under self-similar input traffic. Router is modelled as single server queueing system.  Markov modulated Poisson process (MMPP) is employed to emulate self-similar Internet traffic and the same is used as input process of queueing system. The service times (packet lengths) is assumed to be follow Hyper-Erlang (HE_(p,q)) distribution with p stages in parallel and q phases in series of service. Finally, Internet router is modelled as MMPP/HE_(p,q)/1/K queueing system. The performance measure, namely, mean waiting time (MWT) is computed and presented graphically.

 

 

 

INTRODUCTION:

It is evident from earlier studies that Internet protocol (IP) traffic of both Ethernet traffic and wide area network (WAN) traffics are self-similar or long range dependent (LRD) [1, 2, 3]. Such traffic has impact on network nodes such as Internet routers or switches. Markov modulated Poisson process (MMPP) is employed to emulate the self-similar traffic over the desired time-scales [4, 5, 6]. The network performance measure such as packet delay is significant in dimensioning the router. In general, there are two types of networks: synchronous (slotted) and asynchronous (unslotted) [7]. In the case of first one, all the packets are of same size [8, 9] and in the asynchronous networks, all the packets are of different lengths and are not aligned before they enter the networks [10, 11, 12]. Since IP packets are, in general, variable in length and the router is required to possess the ability to switch the variable length packets.

 

Therefore, performance analysis of the router by means of MMPP/D/1/K queueing system, wherein service time (packet length) is deterministic, may not be appropriate [9]. Router with variable length packet traffic is modelled as MMPP/M/1/K queueing system wherein service time is exponential distribution [13, 14, 15, 16]. Hyper-Erlang distribution (HE_(p,q)) with p stages in parallel and q phases in series of service is more general and includes Erlang-q distribution (E_q), Hyper-exponential distribution (H_p), and exponential distribution [17]. Therefore, it is more appropriate for variable length packet distribution. In this paper, we analyze the router performance measure, namely, mean waiting time (MWT) using MMPP/HE_(p,q)/1/K queueing system. Following the papers [18, 9], a recurrence formula to compute the matrices of counting function is derived in the case of Hyper-Erlang service times.

 

The rest of the paper is organized as follows: In section 2, modeling and performance analysis of the router is briefly discussed. Numerical results are presented graphically in section 3. Finally, conclusion is given in section 4.

 

 

2. Modeling and Performance Analysis of the Router:

Asynchronous Internet router with self-similar variable length packet traffic input here is modelled as MMPP/HE_(p,q)/1/K queueing system. Markov modulated Poisson process (MMPP) is fitted for self-similar traffic.In MMPP/HE_(p,q)/1/K system, the packets arrive according to the MMPP of states m and is characterized by the matricesand, whereandareorder matrices. The mean arrival rateof MMPP is given by, whereis the steady state vector ofand satisfies, whereis the column vector consisting of all ’s with appropriate dimension. The service time (packet length) distribution  is assumed to follow Hyper-Erlang (HE_(p,q)) distribution withstages in parallel andphases in series of service. The probability density functionof Hyper-Erlang service times is

 

                                                                                                                                (1)

 

whereis the initial probability vector withandforare the mean service rate of each stage of service,. The overall mean service time is,. Then the traffic intensity is. Letdenote the  matrices of orderwhose element is the probability that given departure at time, which left at least one packet in the system and the process is in state, the next departure occurs when the arrival process in, and during that service time there werearrivals in the system. Then matrices of counting function’s satisfy the following equation [18, 9],

 

                                                                                                                  (2)

 

Since the service time distributionis Hyper-Erlang distribution, we have,

 

                                                                                                             (3)

 

Forin equation (3), we have,

 

                                                                                                             (4)

 

For, letbe the coefficient ofin, term  of the series on right hand side of equation (3).  Then we have,

 

, , ..., , if ,

and

.

 

Now, multiply on both sides of above equation by, we obtain

 

.

 

.

 

 

 

In above equation, equating the coefficients of like powers of, we obtain,

 

, , … .

From equation (2), we have

 

for .                                                                                                                      (5)

 

We compute the matrices of counting function’s, using the recurrence formulae equations (4) and (5). Now we consider the embedded Markov chainat the departure epochs of the MMPP/HE_(p,q)/1/K queueing system on the state spacewheredenotes the buffer occupancy anddenotes the state of the MMPP. For convenience, a queueing system is said to be at level, if its buffer occupancy is equal to(excluding the ones in service). Then the pertaining embedded Markov chain has transition probability matrix with dimension (),

 

 ,                                                                                                   (6)

 

whereconsisting of conditional probabilities that system is not busy and. Let,  where, for, andis the stationary probability vector that the number of departing packets leaves packets in the system given that embedded Markov chain is in thestate. Therefore, we have. We compute the mean waiting time (MWT) using the following formula [10],

 

                                                                                                                                 (7)

 

3. Numerical Results:

We compute the steady state mean waiting time (MWT) by using matrix-geometric solution technique [19, 20, 21, 13, 16, 22, 23]. We follow the generalized variance based Markovian fitting method to fit the MMPP that emulate the second order self-similar traffic input [6]. We employ three different traffic corresponding to the Hurst parameter values,, and. The mean arrival rate and variance of the self-similar traffic is set to be1 and, respectively [6], and the interested time-scale range to emulate self-similarity are over, , , and . The numerical calculations are performed using MATLAB software. The number of superposed two state MMPPs, () is taken to be. The buffer depthof the router is set to be.The packet length is assumed to follow Hyper-Erlang distribution withstages in parallel andphases in series of service. The characteristics of Hyper-Erlang distribution,is set to beand, , , , , where is the overall mean service rate. The numerical results are presented in Figs.1-3. From Figs.1-3, depicts mean waiting time (MWT) against traffic intensity. From (Fig.1) presents the results for the case of various Hurst parameters and time-scales. From (Fig.2) depicts the results for the case of Hurst parameters,, , and over the various time-scales. From (Fig.3) illustrates the results for the case of the time-scales over, , , and  with the various Hurst parameters. From the Figs.1-3, it is clear that mean waiting time (MWT) increases as traffic intensity increases.

 

 

Fig.1: Variation of mean waiting time against traffic intensity with the various Hurst parameters and time-scales

 

Fig.2: Variation of mean waiting time against traffic intensity with the various Hurst Parameters and time-scales

 

 

Fig. 3: Variation of mean waiting time against traffic intensity over the various time-scales and Hurst parameters

 

4. CONCLUSION:

We investigate the delay behaviour of asynchronous Internet router using MMPP/HE_(p,q)/1/K queueing system. The mean waiting time (MWT) is computed using matrix geometric solution and the numerical results are presented graphically against the system parameters and traffic parameters. With this analysis, it is conclude that mean waiting time is sensitive with respect to system parameters and traffic parameters. This kind of study is important for the dimension of the router.

 

5.   REFERENCES:

1.       Paxson V, Floyd S. Wide area traffic: the failure of Poisson modeling, IEEE/ACM Transactions on Networking. 1995; 3(3): 226-244.

2.       Leland WE, Taqqu MS, Willinger W, Wilson DV. On the self-similar nature of Ethernet traffic (Extended Version), IEEE/ACM Transactions on Networking. 1994; 2(1): 1-15.

3.       Crovella ME,Bestavros A. Self-similarity in world wide web traffic: evidence and possible causes, IEEE/ACM Transactions on Networking. 1997;  5(6): 835-846.

4.       Anderson AT, Nielsen BF. A Markovian approach for modeling packet traffic with long-range dependence,IEEE Journal on Selected Areas in Communications. 1998; 16(5): 719-732.

5.       Yoshihara T, Kasahara S, Takahashi Y. Practical time-scale fitting of self-similar traffic with Markov-modulated Poisson process, Telecommunication Systems. 2001; 17(1): 185-211.

6.       Shao SK, Reddy PM, Tsai MG, Tsao HW, Wu J. Generalized variance-based Markovian fitting for self-similar traffic modeling, IEICE Transactions on Communications.2005; E88-B(4): 1493-1502.

7.       Qiao C, Yoo M. Optical burst switching (OBS); A new paradigm for an optical Internet, Amsterdam Journal of High Speed Networks. 1999; 8(1): 69-84.

8.       Chen CY, Chang CH, Reddy PM, Shao SK,Wu J. Performance analysis of  WDM optical packet switches employing wavelength conversion under Markovian modeled  self-similar traffic input,IEEE HPSR 2007 workshop on High Performance Switching and Routing, Brooklyn, New York, USA.30^th May-1^st June 2007; 1-6.

9.       Reddy PM, Shao SK, Chang CH, Wu J. An efficient approximate Markovian model for optical packet switches employing partial buffer sharing mechanism under self-similar traffic input,IEEE HPSR 2007 workshop on High Performance Switching and Routing, Brooklyn, New York, USA. 30^th May-1^st June 2007; 1-7.

10.     Collegati F. Approximate modeling of optical buffers for variable length packets, Photonic Network Communications. 2001; 3(4): 383-390.

11.     Kumar KS, Reddy PM,Adilakshmi T. Performance study of WDM OPS employing tuneable converter sharing under self-similar variable length packet traffic,18^th IEEE International Conference on Networks (ICON 2012) Singapore, 12^th-14^th December 2012; 114-119.

12.     Reedy PM, Kumar LPR, Reddy DM, Kumar KS. Performance analysis of Internet router employing partial buffer sharing mechanism under Markovian modelled self-similar variable length packet input traffic,Academic International Journal of Pure and Applied Mathematics. 2011; 67(4): 407-421.

13.     Lucantoni DM. New results on the single server queue with a batch Markovian arrival process, Taylor and Francis Communications in Statistics-Stochastic Models. 1991; 7(1): 1-46.

14.     Reddy PM, Kumar LPR, Kumar KS, Shao SK. Analytical model for the switch handling self-similar traffic with variable packet length, 16^th  IEEE International Conference on Networks (ICON 2008) New Delhi. 12^th-14^th December 2008; 1-5.

15.     Kumar LPR, KumarKS, Reddy DM, Reddy PM. Analytical model for performance study of the switch under self-similar variable length packet traffic, The World Congress on Engineering and Computer Science (WCECS 2010) San Francisco, USA. 20^th-22^nd October, 2010; 243- 247.

16.     Kumar LPR, Kumar KS, Reddy DM, Reddy PM. Analytical model for loss and delay behavior of the switch under self-similar variable length packet input traffic, IAENG International Journal of Computer Science.2011; 38(1): 103-112.

17.     Fang  Y. Hyper-Erlang distribution model and its application in wireless mobile networks,Wireless Networks.2001; 7: 211-219.

18.     Venkataramani B, Bose SK, Srivathsan KR. Queuing analysis of a non-pre-emptive MMPP/D/1 priority system, Elsevier Computer Communications. 1997; 20(11): 999-1018.

19.     Blondia C. The N/G/1 finite capacity queue, Taylor and Francis Communications in Statistics-Stochastic Models.1989; 5(2): 273-294.

20.     Lucantoni DM, Hellstern KSM,Neuts MF. A single-server queue with server vacations and a class of non-renewal arrival processes, Advances in Applied Probability. 1990; 22(3): 676-705.

21.     Latouche G, Ramaswamy V. Introduction to matrix analytic methods in stochastic modeling, SIAM Press, Philadelphia, 1999.

22.     Neuts MF. Matrix-geometric solutions in stochastic models: An algorithmic approach, Dover Publications, New York, 1995.

23.     Kasahara S. Internet traffic modeling: Markovian approach to self-similar traffic and prediction of loss probability for finite queues, Special Issue on Internet Technology, IEICE Transactions on Communications.2001; E84-B(8): 2134-2141.

 

 

 

 

Accepted on 25.10.2017      ©A&V Publications All right reserved

Research J. Science and Tech. 2017; 9(4): 686-690.